// Dijkstra's algorithm
// / # source-mat
function dijkstra(
  edges: [string, string, number][],
  source: string,
  target: string,
) {
  const Q = new Set<string>();
  const prev: Record<string, string> = {};
  const dist: Record<string, number> = {};
  const adj: Record<string, Record<string, number>> = {};

  // eslint-disable-next-line @typescript-eslint/prefer-for-of
  for (let i = 0; i < edges.length; i++) {
    const [v1, v2, len] = edges[i];
    // wrapper method
    initQ.bind({ Q, dist, adj })(v1, v2, len);
    // Q.add(v1);
    // Q.add(v2);

    // dist[v1] = Infinity;
    // dist[v2] = Infinity;

    // if (adj[v1] === undefined) adj[v1] = {};
    // if (adj[v2] === undefined) adj[v2] = {};

    // adj[v1][v2] = len;
    // adj[v2][v1] = len;
  }
  // / start from `source`
  dist[source] = 0;
  // doFind
  while (Q.size) {
    const u = vertexWithMinDist(Q, dist);
    if (u === null) continue;
    const neighbors = Object.keys(adj[u]).filter((v) => Q.has(v)); // Neighbor still in Q

    Q.delete(u);

    if (u === target) break; // Break when the target has been found

    for (const v of neighbors) {
      const alt = dist[u] + adj[u][v];
      if (alt < dist[v]) {
        dist[v] = alt;
        prev[v] = u;
      }
    }
  }

  let u = target;
  const S = [u];
  let len = 0;

  while (prev[u] !== undefined) {
    S.unshift(prev[u]);
    len += adj[u][prev[u]];
    u = prev[u];
  }
  return [S, len] as const;

  /**
   * 从给定的集合 Q 中找到距离最小的顶点
   * @param Q - 包含顶点的集合
   * @param dist - 记录每个顶点距离的对象
   * @returns 距离最小的顶点，如果 Q 为空则返回 null
   */
  function vertexWithMinDist(
    Q: Set<string>,
    dist: Record<string, number>,
  ): string | null {
    let minDistance = Infinity;
    let u = null;

    for (const v of Q) {
      if (dist[v] < minDistance) {
        minDistance = dist[v];
        u = v;
      }
    }
    return u;
  }
  // out-pack method
  function initQ(
    this: {
      Q: Set<string>;
      dist: Record<string, number>;
      adj: Record<string, Record<string, number>>;
    },
    v1: string,
    v2: string,
    len: number,
  ) {
    this.Q.add(v1);
    this.Q.add(v2);

    this.dist[v1] = Infinity;
    this.dist[v2] = Infinity;

    if (this.adj[v1] === undefined) this.adj[v1] = {};
    if (this.adj[v2] === undefined) this.adj[v2] = {};

    this.adj[v1][v2] = len;
    this.adj[v2][v1] = len;
  }
}

// export = { dijkstra };

// Testing algorithm
const graph: [string, string, number][] = [];
graph.push(["a", "b", 7]);
graph.push(["a", "c", 9]);
graph.push(["a", "f", 14]);
graph.push(["b", "c", 10]);
graph.push(["b", "d", 15]);
graph.push(["c", "d", 11]);
graph.push(["c", "f", 2]);
graph.push(["d", "e", 6]);
graph.push(["e", "f", 9]);
// TODO: use D3
const [path, length] = dijkstra(graph, "a", "e");
console.log(path); // [ 'a', 'c', 'f', 'e' ]
console.log(length); // 20

// const b = [1, 2, 3] as unknown as [number, number, string];
// //    ^?
// type e = EventTarget extends Event ? 1 : 0;
// //   ^?
